package leetcode;

//Input: [7, 1, 5, 3, 6, 4]
//Output: 5
//max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price)
public class BestTimeToSellStock {
	public static void main(String[] args) {
//		int[] num = new int[] { 1, 2, 4, 2, 5, 7, 2, 4, 9, 0 };
//		int[] num = new int[] { 1, 2, 3, 0, 2};
//		maxProfit(num);
//		maxProfit2(num);
//		maxProfit3_2(num);
//		maxProfitCoolDown(num);
		
		BestTimeToSellStock object = new BestTimeToSellStock();
		int[] prices = {5, 7, 8, 9, 3, 10, 6, 2, 4, 1, 3, 5};
		System.out.println(object.maxProfitMostK(3, prices));
	}

	// just can buy and sell once
	public static int maxProfit(int[] num) {
		if (num == null || num.length <= 0) {
			System.err.println("the wrong input");
			return 0;
		}
		int leftMin = num[0]; // 在i之前数组中最小的元素
		int maxProfit = 0; // 最大收益
		for (int i = 1; i < num.length; i++) {
			if (num[i] > leftMin) {
				maxProfit = Math.max(maxProfit, num[i] - leftMin);
			} else if (num[i] < leftMin) {
				leftMin = num[i];
			}
		}
		System.out.println(maxProfit);
		return maxProfit;
	}

	// you can buy and sell multiple times, but you may not engage in multiple
	// transactions at the same time
	// that means you must sell the stock before you buy again
	public static int maxProfit2(int[] num) {
		if (num == null || num.length <= 0) {
			// System.err.println("the wrong input");
			return 0;
		}
		// int leftMin = num[0]; // 在i之前数组中最小的元素
		// int curProfit = 0; // 当前收益
		int maxProfit = 0; // 最大收益
		for (int i = 1; i < num.length; i++) {
			// 看来自己还要学会总结问题啊，让代码看上去更加精简
			// 中心思想就是如果下一天的价格大于当前价格则下一天卖的利润大
			// 如果前一天的价格小于当前的价格，则前一天的价格买的利润大
			if (num[i] > num[i - 1]) {
				maxProfit += num[i] - num[i - 1];
			}
			// if (num[i] > leftMin) {
			// // 中心思想就是如果下一天的价格大于当前价格则下一天卖的利润大
			// // 如果前一天的价格小于当前的价格，则前一天的价格买的利润大
			// if (i < num.length - 1 && num[i + 1] < num[i]) {
			// curProfit = num[i] - leftMin; // curProfit
			// maxProfit += curProfit;
			// leftMin = num[i + 1];
			// } else if (i == num.length - 1) {
			// curProfit = num[i] - leftMin; // curProfit
			// maxProfit += curProfit;
			// }
			// } else if (num[i] < leftMin) {
			// leftMin = num[i];
			// }
		}
		System.out.println(maxProfit);
		return maxProfit;
	}

	// wrong Solution :the max two Profit of all the profit(maxProfit2) maybe
	// not be the max profit
	// e.g. 1,2,4,2,5,7,2,4,9
	// the all profit is 3 5 7(use maxProfit2),and then the sum of first and
	// second
	// is 12
	// However , if you buy in 1, sell in 7, the progit will be 6, and the next
	// profit is 7(buy 2, sell 9) ,sum is 13

	// you can only make two transactions
	public static int maxProfit3(int[] num) {
		if (num == null || num.length <= 0) {
			// System.err.println("the wrong input");
			return 0;
		}
		int leftMin = num[0]; // 在i之前数组中最小的元素
		int curProfit = 0; // 当前收益
		int maxProfit = 0, secondProfit = 0; // 记录最大和第二大收益
		for (int i = 1; i < num.length; i++) {
			if (num[i] > leftMin) {
				// 中心思想就是如果下一天的价格大于当前价格则下一天卖的利润大
				// 如果前一天的价格小于当前的价格，则前一天的价格买的利润大
				if (i < num.length - 1 && num[i + 1] < num[i]) {
					curProfit = num[i] - leftMin; // curProfit
					if (curProfit >= maxProfit) {
						secondProfit = maxProfit;
						maxProfit = curProfit;
					} else if (curProfit >= secondProfit) {
						secondProfit = curProfit;
					}
					System.out.println("max" + maxProfit + "sec "
							+ secondProfit);
					leftMin = num[i + 1];
				} else if (i == num.length - 1) {
					curProfit = num[i] - leftMin; // curProfit
					if (curProfit >= maxProfit) {
						secondProfit = maxProfit;
						maxProfit = curProfit;
					} else if (curProfit >= secondProfit) {
						secondProfit = curProfit;
					}
					System.out.println("max" + maxProfit + "sec "
							+ secondProfit);
				}
			} else if (num[i] < leftMin) {
				leftMin = num[i];
			}
		}
		System.out.println(maxProfit + secondProfit);
		return maxProfit + secondProfit;
	}

	// sell1 means we decide to sell the stock, after selling it we have
	// price[i] money and
	// we have to give back the money we owed, so we have price[i] - |buy1| =
	// prices[i ] + buy1,
	// we want to make this max.

	// buy2 means we want to buy another stock, we already have sell1 money, so
	// after buying stock2
	// we have buy2 = sell1 - price[i] money left, we want more money left, so
	// we make it max

	// sell2 means we want to sell stock2, we can have price[i] money after
	// selling it,
	// and we have buy2 money left before, so sell2 = buy2 + prices[i], we make
	// this max.

	// So sell2 is the most money we can have.
	public static int maxProfit3_2(int[] prices) {
		if (prices == null || prices.length <= 0) {
			System.err.println("the wrong input");
			return 0;
		}
		int buy1 = Integer.MIN_VALUE; // 第一次买股票之后手里剩下的钱，由于初始值为0，故会是-price[i]
		int profit1 = Integer.MIN_VALUE; // 第一次卖股票的时候手里剩下的钱

		int buy2 = Integer.MIN_VALUE; // 第二次买股票之后手里剩下的钱
		int allProfit = Integer.MIN_VALUE;  //第二次卖股票后的收益

		for (int i = 0; i < prices.length; i++) {
			buy1 = Math.max(buy1, -prices[i]);
			profit1 = Math.max(profit1, prices[i] + buy1);
			// buy1 = Math.min(buy1, prices[i]);
			// profit1 = Math.max(profit1, prices[i] - buy1);

			buy2 = Math.max(buy2, profit1 - prices[i]);
			allProfit = Math.max(allProfit, prices[i] + buy2);
			System.out.println(prices[i] + " buy1 " + buy1 + " profit1 "
					+ profit1 + " buy2 " + buy2 + " sell2 " + allProfit);
		}

		return allProfit;
	}

	// Best Time to Buy and Sell Stock with Cooldown
	// After you sell your stock, you cannot buy stock on next day. (ie,
	// cooldown 1 day)

	// 一共有三种状态了，buy之后，sell之后以及休息，休息包括不买不卖以及卖之后强制的休息
	public static int maxProfitCoolDown(int[] prices) {
		if (prices == null || prices.length <= 0) {
			return 0;
		}
		int buy = -prices[0]; // 初始为买第0天后的钱
		int sell = Integer.MIN_VALUE;
		int rest = 0; // 不买的话初始为0

		for (int i = 1; i < prices.length; i++) {
			System.out.println(i + " buy: " + buy + " rest: " + rest + " prices[i]: " + prices[i]);
			//要注意这里执行的顺序，由于每一次转移都是在上一次执行的基础之上的
			buy = Math.max(buy, rest - prices[i]);
			//不能先更新sell再更新rest
			rest = Math.max(rest, sell);
			sell = buy + prices[i];
		}
		System.out.println("the max profit: " + Math.max(rest, sell));
		return Math.max(rest, sell);
	}
	
	//最多买卖k次
	public int maxProfitMostK(int k, int[] prices) {
        if(k <= 0){
            return 0;
        }
        int len = prices.length;
        //如果k满足可以买卖任意多次的要求
        if (k >= len / 2) return quickSolve(prices);
        
        //dp[i][j]表示prices[0...i]最多买卖j次时最大的利润
        int[][] dp = new int[len][k + 1];
        int temp = 0;
        //dp[m][j - 1]表示0...m买卖j - 1次, 另一次是prices[i] - prices[m]
        //dp[i][j] = max(dp[i - 1][j], dp[m][j - 1] + prices[i] - prices[m])
        for (int j = 1; j <= k; j++) {
        	temp = dp[0][j - 1] - prices[0];
        	for(int i = 1; i < len; i++){
				dp[i][j] = Math.max(dp[i - 1][j], prices[i] + temp);
				temp = Math.max(temp, dp[i][j - 1] - prices[i]);
			}
        }
        for (int i = 0; i < len; i++) {
			for (int j = 0; j <= k; j++) {
				System.out.print(dp[i][j] + "  ");
			}
			System.out.println();
		}
        return dp[len - 1][k];
    }
	
	private int quickSolve(int[] prices) {
        int len = prices.length, profit = 0;
        for (int i = 1; i < len; i++)
            // as long as there is a price gap, we gain a profit.
            if (prices[i] > prices[i - 1]) profit += prices[i] - prices[i - 1];
        return profit;
    }
	
}
